package 字节;



import org.w3c.dom.Node;

import java.util.HashMap;

public class LRU {

    int capacity;
    class Node{
        Node pre;
        Node next;
        int key;
        int val;
        public Node(){};
        public Node(int key,int val){
            this.val=val;
            this.key=key;
        }
    }

    Node head;
    Node tail;
    HashMap<Integer, Node> hashMap;
    public LRU(int capacity){
        this.capacity=capacity;
        hashMap=new HashMap<>(capacity);
    }

    int get(int key){
        Node node=hashMap.get(key);
        if(node==null){
            return -1;
        }else {
            makeRecently(node);
            return node.val;
        }
    }

    void put(int key,int val){
        Node node=hashMap.get(key);
        if(node==null){
            if(hashMap.size()==capacity){
                removeLast();
            }
            Node node1=new Node(key,val);
            addTohead(node1);
            hashMap.put(key,node1);
        }else {
            node.val=val;
            hashMap.put(key,node);
            makeRecently(node);
        }
    }

    void makeRecently(Node node){
        if(node==head){
            return;
        }else if(node==tail){
            tail.pre.next=null;
            tail=tail.pre;
        }else {
            remove(node);
        }

        addTohead(node);
    }

    void removeLast(){
        hashMap.remove(tail.key);
        Node node=tail.pre;
        if(node!=null){
            node.next=null;
            tail=node;
        }


    }

    void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }

    void addTohead(Node node){
        if(hashMap.isEmpty()){
            head=node;
            tail=node;
        }else {
            node.next=head;
            head.pre=node;
            head=node;
        }

    }

    public static void main(String[] args) {
        LRU cache = new LRU(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1);
        cache.put(4, 3);
        System.out.println(cache);
    }
}

class LRUCache{
    int capacity;
    class Node{
        Node pre;
        Node next;
        int key;
        int val;
        public Node(){};
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }

    Node head;
    Node tail;
    HashMap<Integer, Node> hashMap;
    public LRUCache(int capacity){
        this.capacity=capacity;
        hashMap=new HashMap<>(capacity);
    }

    int get(int key){
        Node node=hashMap.get(key);
        if(node==null){
            return -1;
        }
        makeRecently(node);
        return node.val;
    }

    void makeRecently(Node node){
        if(node==head){
            return;
        }else if(node== tail){
            tail.pre.next=null;
            tail=tail.pre;
        }else {
            remove(node);
        }
        addTohead(node);
    }

    void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }

    void addTohead(Node node){
        if(hashMap.isEmpty()){
            head=node;
            tail=node;
        }else {
            node.next=head;
            head.pre=node;
            head=node;
        }
    }

    void put(int key,int value){
        Node node=hashMap.get(key);
        if(node==null){
            if(hashMap.size()==capacity){
                removeLast();
            }
            Node node1=new Node(key,value);
            addTohead(node1);
            hashMap.put(key,node1);
        }else {
            node.val=value;
            hashMap.put(key,node);
            makeRecently(node);
        }
    }

    void removeLast(){
        hashMap.remove(tail.key);
        Node node=tail.pre;
        node.next=null;
        tail=node;
    }
    @Override
    public String toString() {
        return hashMap.keySet().toString();
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1);
        cache.put(4, 3);
        System.out.println(cache);
    }
}
